package _binary_tree

import common.TreeNode
import org.junit.Assert
import org.junit.Test
import java.util.*

/*
https://programmercarl.com/%E5%91%A8%E6%80%BB%E7%BB%93/20201003%E4%BA%8C%E5%8F%89%E6%A0%91%E5%91%A8%E6%9C%AB%E6%80%BB%E7%BB%93.html#%E5%91%A8%E4%B8%80
https://leetcode.cn/problems/subtree-of-another-tree/description/
572. 另一棵树的子树
示例 1：
输入：root = [3,4,5,1,2], subRoot = [4,1,2]
输出：true

示例 2：
输入：root = [3,4,5,1,2,null,null,null,null,0], subRoot = [4,1,2]
输出：false
 */
class leetcode_572 {
    @Test
    fun test_1() {
        val n1 = TreeNode(1)
        val n2 = TreeNode(2)
        val n3 = TreeNode(3)
        val n4 = TreeNode(4)
        val n5 = TreeNode(5)
        val root1 = n3
        root1.left = n4
        root1.right = n5
        n4.left = n1
        n4.right = n2
        val n1_v1 = TreeNode(1)
        val n2_v2 = TreeNode(2)
        val n4_v2 = TreeNode(4)
        val root2 = n4_v2
        root2.left = n1_v1
        root2.right = n2_v2

        val actual = isSubtree(root1, root2)
        val expect = true
        Assert.assertEquals(expect, actual)
    }

    @Test
    fun test_2() {
        val n0 = TreeNode(0)
        val n1 = TreeNode(1)
        val n2 = TreeNode(2)
        val n3 = TreeNode(3)
        val n4 = TreeNode(4)
        val n5 = TreeNode(5)
        val root1 = n3
        root1.left = n4
        root1.right = n5
        n4.left = n1
        n4.right = n2
        n2.left = n0

        val n1_v1 = TreeNode(1)
        val n2_v2 = TreeNode(2)
        val n4_v2 = TreeNode(4)
        val root2 = n4_v2
        root2.left = n1_v1
        root2.right = n2_v2

        val actual = isSubtree(root1, root2)
        val expect = false
        Assert.assertEquals(expect, actual)
    }

    private fun isSubtree(root: TreeNode?, subRoot: TreeNode?): Boolean {
        /**
         * 题型：二叉树的层次遍历 + 前序遍历
         *
         * 思路：
         * 使用层次遍历root，若节点与subRoot 值相同，然后使用前序遍历判断节点与subRoot是否相同的树。
         */

        // 结束条件
        if (null == root && subRoot == null) {
            return false
        }
        if (null == root && subRoot != null) {
            return false
        }
        if (null != root && subRoot == null) {
            return false
        }
        val queue: LinkedList<TreeNode> = LinkedList<TreeNode>()
        queue.offer(root)
        while (!queue.isEmpty()) {
            var size = queue.size
            while (size-- > 0) {
                val p: TreeNode = queue.poll()
                // 找到值相同的节点，然后判断是否相等
                if (p.`val` == subRoot?.`val`) {
                    val isSame = isSameTree(p, subRoot)
                    if (isSame) {
                        return true
                    }
                }
                p.left?.let { queue.offer(it) }
                p.right?.let { queue.offer(it) }
            }
        }
        return false
    }

    val leetcode_100 = leetcode_100()
    private fun isSameTree(p: TreeNode?, q: TreeNode?): Boolean {
        return leetcode_100.isSameTree(p, q)
    }
}